あるところに仲良し9人グループがいました。
リーダーのタカ、サプリーダーのヒデを中心とした個性豊かな良いグループです。
あるとき、ぶきっちょだけど元気なミキちゃんが、3on3のバスケをやりたいと
いいだしました。なるほど、ちょうど3チームに分けられそうです。
みんなのバスケの腕前はお互いによく知っています。
そこで、それを点数化し、表にまとめてみることにしました。
| シュート | ドリブル | パス | 判断力 | |
|---|---|---|---|---|
| Taka | 10 | 10 | 8 | 7 |
| Hide | 8 | 9 | 9 | 10 |
| Nori | 7 | 8 | 6 | 8 |
| Dai | 10 | 3 | 5 | 3 |
| Hiro | 5 | 4 | 5 | 6 |
| Miki | 2 | 7 | 7 | 4 |
| Chika | 4 | 3 | 8 | 5 |
| Nana | 6 | 4 | 5 | 3 |
| Ton | 4 | 3 | 3 | 2 |
さて、これまで扱ってきた問題は単純にある値を最大化したり、最小化したりする問題でした。
しかし、この問題ではばらつきというよくわからないものを最小化する問題です。
世の中ではよく分散(Variance)というものを考えますが、
LPやMIPを用いればもっと自由度の高い考え方ができます。
ここでは最も単純な考え方として、最大-最小をばらつきと考えましょう。
つまりばらつきを最小化するとは、
一番強いチームから弱いチームの力の差を最小にするということになります。
参考: 分散とは
分散とは平均値からのずれ(差)の2乗和のことです。
数式で書けば(1/N)・Σ(Xi - m)^2 です。(mは平均, Nはデータ数)
なぜ2乗するのか、というと、ずれには正負がありますから、単純に足すと
お互いにずれを打ち消してしまうからです。
もちろん絶対値をつけてもよいのですが、微分が難しくなり(原点で微分不可能)
数学的な扱いが困難になるのでふつうはしません。
まず、各能力を全て足しあわせ、各チームごとにその和(つまり総合力)に関して
ばらつきをなくすことを考えましょう。
具体例を挙げましょう。
例えば、Taka,Hide,Noriでチームを作れば
Taka 10+10+8+7 = 35 点
Hide 8+9+9+10 = 36 点
Nori 7+8+6+8 = 29 点
となり、合計は、100点の総合力です。
一方、Chika,Nana,Tonでチームを作れば
Chika 4+3+8+5 = 20
Nana 6+4+5+3 = 18
Ton 4+3+3+2 = 12
となり、合計は、50点の総合力です。
これではあんまりです。どう考えても勝ち目はありません。
チーム作りではこの総合力の差をなるべく小さくすることを考えるのは
ごく自然だと分かってもらえたと思います。
いつものようにGLPKで定式化するには集合が必要です。
人(Person)、属性(Attribute)、
チーム(Team)としましょうか。
PersonはTakaやHideなど、各人を表します。
Attributeはシュートやドリブルなど、各能力の項目を表します。
チームは3つの各チームを表します。
パラメータは当然、能力(skill)が必要です。
これは、人・属性によって変わるのでskill{Person,Attribute}としましょう。
さらに、チーム数(T)もパラメータとしておきます。
この値を変えるだけでチーム数を変えることができ、汎用性が増すからです。
後の節で、このパラメータを使って集合Teamを定義します。
変数は、チームに所属することを表す0-1変数とします。
各人について、どのチームに所属するか分からないので、
δ{Person,Team}とし、9×3 = 計27個の変数を定義します。
例えば、δ[chika,2]=1 ならば、チカがチーム2に所属することを表します。
※0-1変数はδと書くことが多いようです。あとのGLPKのモデルではXを使います。
また、各チームの総合力の最大(max)と最小(min)も
変数として定義します。
このように、最小値最大化問題や最大値最小化問題
やこれに準ずる問題は、その最大値や最小値を変数で表すのが
常套手段です。
目的関数は、総合力の最大と最小の差を最小にすることですから、
max - min → minimize
と書けます。
制約条件はまず、最大値と最小値を決めることから始めましょう。
そもそも最大値とは何かというと、全ての値の中で最も大きいものです。
当たり前ですね？
GLPKでは、これをそのまま書いてやるだけです。
つまり、
各チームの総合力 ≦ max
と書けます。
そして各チームの総合力、とは、チーム内の各人の能力の和です。
チーム内の人だけを足しあわせるには、そう、0-1変数との積をとればいいですね。
なぜなら、チームにいない人に対応する変数は0なので、かけざんすると0になり、
関係なくなるからです。
Σ能力×変数、これがチーム内の各人の能力です。これの和がチームの総合力なので
ΣΣ能力×変数、これが総合力となります。
よって、ΣΣ能力×変数 ≦ max と書けます。
最小値も全く同様に、ΣΣ能力×変数 ≧ min と書けます。
さらに制約条件として、各人は1つのチームにしか参加できない、
そして、必ず1つのチームには参加する、という条件を
加えないといけません。
これがないと、一人が全チームに参加するような妙なことが起きます。
これは、各人に対して各チームに対する変数の値が1になっていることを
保証しなければなりません。
これを表すには、各人に対して、各チームの変数の和=1 だと考えます。
もうひとつ、各チームは3人でなければなりませんでした。
これは、各チームに対して、各人の変数の和=3 だと考えます。
前者は変数の行列を横方向に、後者は縦方向に足したものだとすると
考えやすいと思います。
このイメージを下図に示します。
さて、定式化の方針が立ったので数式で表してみましょう。
これをGLPKで表すと下のようになります。
例によって、数式とほぼ1対1対応しているのが分かると思います。
数式の中でカッコ表記している名称でモデリングしています。
#team.mod
param T;
set Person;
set Attribute;
set Team := 1..T;
param skill{Person,Attribute};
var X{Person,Team} binary;
var max >=0;
var min >=0;
minimize minVariance: max-min;
s.t. Getmax{t in Team}:sum{p in Person, a in Attribute}skill[p,a]*X[p,t] <= max;
s.t. Getmin{t in Team}:sum{p in Person, a in Attribute}skill[p,a]*X[p,t] >= min;
s.t. Identification{p in Person}: sum{t in Team}X[p,t] = 1;
s.t. Number{t in Team}: sum{p in Person}X[p,t] = 3;
#team.dat param T := 3; set Person := taka hide nori dai hiro miki chika nana ton; set Attribute := shoot dribble pass estimation; param skill: shoot dribble pass estimation:= taka 10 10 8 7 hide 8 9 9 10 nori 7 8 6 8 dai 10 3 5 3 hiro 5 4 5 6 miki 2 7 7 4 chika 4 3 8 5 nana 6 4 5 3 ton 4 3 3 2;
モデル上で注目して頂きたいのは、集合Teamの定義の仕方です。
param T;
(中略)
set Team := 1..T;
今までにない定義の仕方ではないですか？
これは、パラメータでチーム数を与え、1..Tという形で
集合を与えているのです。
何となく分かると思いますが、1..Tで、1〜Tまでの数字が全て集合要素になります。
実際に、データファイルでT:=3; と定義されているので、
Teamは1 2 3を要素とする集合になります。
この定義は数が増えてもすぐに対応できて便利なので覚えておくと良いでしょう。
注意点として、モデルファイル上で集合より先に与えるパラメータを定義しておかないと
エラーになるので気をつけてください。
ここではparam T;を先に書いていると思います。
解いた結果は以下に示します。
Problem: team
Rows: 19
Columns: 29 (27 integer, 27 binary)
Non-zeros: 116
Status: INTEGER OPTIMAL
Objective: minVariance = 4 (MINimum) 0 (LP)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 minVariance 4
2 Getmax[1] -4 0
3 Getmax[2] 0 0
4 Getmax[3] -4 0
5 Getmin[1] 0 0
6 Getmin[2] 4 0
7 Getmin[3] 0 0
8 Identification[taka]
1 1 =
9 Identification[hide]
1 1 =
10 Identification[nori]
1 1 =
11 Identification[dai]
1 1 =
12 Identification[hiro]
1 1 =
13 Identification[miki]
1 1 =
14 Identification[chika]
1 1 =
15 Identification[nana]
1 1 =
16 Identification[ton]
1 1 =
17 Number[1] 3 3 =
18 Number[2] 3 3 =
19 Number[3] 3 3 =
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 X[taka,1] * 0 0 1
2 X[hide,1] * 0 0 1
3 X[nori,1] * 1 0 1
4 X[dai,1] * 0 0 1
5 X[hiro,1] * 1 0 1
6 X[miki,1] * 0 0 1
7 X[chika,1] * 1 0 1
8 X[nana,1] * 0 0 1
9 X[ton,1] * 0 0 1
10 X[taka,2] * 1 0 1
11 X[hide,2] * 0 0 1
12 X[nori,2] * 0 0 1
13 X[dai,2] * 0 0 1
14 X[hiro,2] * 0 0 1
15 X[miki,2] * 1 0 1
16 X[chika,2] * 0 0 1
17 X[nana,2] * 1 0 1
18 X[ton,2] * 0 0 1
19 X[taka,3] * 0 0 1
20 X[hide,3] * 1 0 1
21 X[nori,3] * 0 0 1
22 X[dai,3] * 1 0 1
23 X[hiro,3] * 0 0 1
24 X[miki,3] * 0 0 1
25 X[chika,3] * 0 0 1
26 X[nana,3] * 0 0 1
27 X[ton,3] * 1 0 1
28 max 73 0
29 min 69 0
End of output
結果を見るとObjective:4 なので、チームの総合力の差を
4ポイントにできたことが分かります。
では、実際どういうチーム分けになったかというと、
変数の欄のActivityを見れば分かります。
これではいささか見づらいので、下に表としてまとめておきましょう。
| メンバー名 | シュート | ドリブル | パス | 判断力 | 合計 |
|---|---|---|---|---|---|
| nori | 7 | 8 | 6 | 8 | 29 |
| hiro | 5 | 4 | 5 | 6 | 20 |
| chika | 4 | 3 | 8 | 5 | 20 |
| 合計 | 16 | 15 | 19 | 19 | 69 |
| メンバー名 | シュート | ドリブル | パス | 判断力 | 合計 |
|---|---|---|---|---|---|
| taka | 10 | 10 | 8 | 7 | 35 |
| miki | 2 | 7 | 7 | 4 | 20 |
| nana | 6 | 4 | 5 | 3 | 18 |
| 合計 | 18 | 21 | 20 | 14 | 73 |
| メンバー名 | シュート | ドリブル | パス | 判断力 | 合計 |
|---|---|---|---|---|---|
| hide | 8 | 9 | 9 | 10 | 36 |
| dai | 10 | 3 | 5 | 3 | 21 |
| ton | 4 | 3 | 3 | 2 | 12 |
| 合計 | 22 | 15 | 17 | 15 | 69 |
なかなか良いグループ分けができていると思います。
各項目の和を見てみると、
チーム1はバランスタイプ、チーム2はフィジカルタイプ、チーム3はシュータータイプと
個性がガラっと現れている割には、総合力に大きな差は見られません。
これならおもしろいゲームができそうですね。
めでたし、めでたし。
さて、ここで学んだのは
最大値や最小値を扱う場合の定式化と、
a..bの書式で集合を定義する方法です。
今回のような最大値最小化問題、最小値最大化問題の定式化は、LPでも可能です。
しかし、最大値最大化問題や、最小値最小化問題では
今回のような定式化はできないので注意してください。
試しに、minimizeの条件をmaximizeにして解いてみてください。
UNBOUND SOLUTIONと表示されたことでしょう。
これは制約が弱く、いくらでも値を大きくできることを意味しています。
そのような問題はMIPでないと定式化できません。(条件のor結合というものを使います)
これについても、いずれ取り扱うことにしましょう。